Masala #0178

Xotira 32 MB Vaqt 1000 ms Qiyinchiligi 25 %

Matritsaning maksimal yig'indisi

Sizga 2N×2N o’lchamli matritsa berilgan. Siz 0 yoki bir necha marotaba matritsaning ixtiyoriy qatori yoki ixtiyoriy ustunini tanlab teskarisiga o’girishingiz mumkin. Shundan so’ng siz matritsaning yuqori chap burchagidagi N×N qism matritsaning yig’indisini hisoblaganingizda maksimal necha qiymatga ega bo’lishingiz mumkinligini aniqlang.

Masalan:

1	2	→	1	2	→	4	2
3	4	→	4	3	→	1	3

Kiruvchi ma'lumotlar:

Dastlabki satrda bitta butun son, N(1 ≤ N ≤ 500), keyingi 2N qatorning har birida bo’sh joy bilan ajratilgan holda 2N ta [0, 10⁶] oralig’idagi sonlar kiritiladi.

Chiquvchi ma'lumotlar:

Ixtiyoriy marotaba matritsaning ixtiyoriy qatori yoki ixtiyoriy ustunini teskarisiga aylantirishdan so’ng yuqori chap N×N qism matrisada maksimal yig’indi necha bo’lishini aniqlang.

Misollar

#	input.txt	output.txt
1	1 1 2 3 4	4
2	2 112 42 83 119 56 125 56 49 15 78 101 43 62 98 114 108	414

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin